1. Field of the Invention
The present invention is directed to computer systems. More particularly, it is directed to coordination mechanisms for concurrent programming in computer systems.
2. Description of the Related Art
In the field of computer systems, considerable effort has been expended on developing techniques to support concurrent access to shared resources. Mutual exclusion locks and monitors represent two traditional concurrent programming synchronization mechanisms. Locks and monitors protect shared resources by separating access to them in time; for example, in one implementation, as long as a given thread of execution retains a lock on an object or resource, no other thread of execution may modify the object, and any other thread attempting to modify the object may be blocked from further execution until the lock is released.
However, locking techniques are known to suffer from several limitations, especially in environments where the shared objects may include complex data structures. First, concurrently executing threads often access disjoint sets of memory locations within the same complex object, and locking may only really be required for the relatively infrequent occasions when two or more threads actually access the same memory locations. Typical locking mechanisms either lock the entire object (which helps to simplify programming), or implement locks of fine granularity to independently protect portions of complex objects in an attempt to increase concurrency. However, fine-grained locking techniques often result in a substantial increase in programming complexity. Second, while holding a lock, a thread may often perform numerous “ordinary” operations that do not require the lock—e.g., between any two memory access instructions that do require the lock, a large number of instructions that do not require the lock may be executed, preventing threads that are blocked on the lock from making progress. Finally, many data structures that are typically protected by locks are often accessed for read-only operations (such as method calls that do not modify any field of the data structure). The reading operations could have been making progress concurrently if it were known that no writes on the data structure were performed during their execution.
The transactional memory programming paradigm has been gaining momentum as an approach of choice for replacing locks in concurrent programming. In transactional memory programming, sequences of concurrent operations may be combined into non-blocking atomic transactions, thus making parts of the code appear to be sequential without the need to use locks. Executing threads indicate transaction boundaries, e.g., by specifying when a transaction starts and when it ends, but do not have to acquire locks on any objects. Transactional memory programming techniques may allow transactions that do not overlap in data accesses to run uninterrupted in parallel; transactions that do overlap may be aborted and retried. One stated goal of transactional memory programming techniques is to remove from the programmer the burden of understanding the interaction among concurrent operations that happen to overlap or modify the same locations in memory. However, while transactions may simplify the programmer's need to reason about concurrency, programmers still have to decide which instructions to include in a transaction. This may leave the programmer with a tradeoff similar to that of locking techniques, between the size of the transactions used and program performance: a reduction of transaction size to enhance performance may lead to added complexity in code design and verification. In addition, many current implementations of transactional memory programming are known to be inefficient, for example because of the overhead of the specific mechanisms used to implement transactions. Explicit transactions may also introduce various programming language issues and complications such as how to support nesting of transactions, I/O during transactions, etc., which may complicate transactional programming even if the transaction mechanisms were made more efficient.